package com.cuz.daileetcode.bat100;

import java.util.Arrays;

public class S字符串有多少个子序列字面值等于T字符串 {

    public static int solution1(String s, String t) {
        if (s == null || t == null) {
            return 0;
        }
        //s长度小于t长度 那么g
        if (s.length() < t.length()) {
            return 0;
        }
        return process(s, t, s.length(), t.length());
    }

    /**
     * s字符串的前sLen个字符 的子序列 可以凑出多少个t.subString(0,tLen)
     * <p>
     * s[0,sLen-1] 子序列字面值和 t[0,tLen-1]相同
     *
     * @param s
     * @param t
     * @param sLen
     * @param tLen
     * @return 种数
     */
    private static int process(String s, String t, int sLen, int tLen) {
        // abc 凑出“” 可以凑出1 中 那就是s的空子序列
        if (tLen == 0) {
            return 1;
        }
        //“” 凑 abc 无论如何没有办法凑出来
        if (sLen == 0) {
            return 0;
        }
        //1 s末尾的字符（sLen）不参与
        // abccd 凑abc 可以直接不使用末尾的d 直接求abcc可以凑出多少abc
        int process1 = process(s, t, sLen - 1, tLen);
        //2.如果s末尾字符（s.charAt(sLen)）和t 末尾字符(tLen) 相同
        //那么 可以让s末尾字符参与
        //abcc 凑abc 让abcc的最后字符c作为子序列的末尾字符 搞定abc的末尾字符
        //那么子问题就是abc 可以凑出多少ab
        if (s.charAt(sLen - 1) == t.charAt(tLen - 1)) {
            process1 += process(s, t, sLen - 1, tLen - 1);
        }
        return process1;
    }

    public static void main(String[] args) {
        //s = "rabbbit", t = "rabbit"
        //输出：3
//        String s = "babgbag";
        String s = "rabbbit";
//        String t = "bag";
        String t = "rabbit";
        System.out.println(solution1(s, t));
        System.out.println(solution2(s, t));
        System.out.println(solution3(s, t));
    }

    //dp
    public static int solution2(String s, String t) {
        if (s == null || t == null) {
            return 0;
        }
        //s长度小于t长度 那么g
        if (s.length() < t.length()) {
            return 0;
        }
        int sLenRow = s.length();
        int tLenCol = t.length();
        int[][] dp = new int[sLenRow + 1][tLenCol + 1];
        //递归的baseCase
        //数组默认就是0
//        for (int i = 0; i < tLenCol + 1; i++) {
//            dp[0][i] = 0;
//        }
        for (int i = 0; i < sLenRow + 1; i++) {
            dp[i][0] = 1;
        }
        for (int row = 1; row < sLenRow + 1; row++) {
            for (int col = 1; col < tLenCol + 1; col++) {
                dp[row][col] = dp[row - 1][col];
                if (s.charAt(row - 1) == t.charAt(col - 1)) {
                    dp[row][col] += dp[row - 1][col - 1];
                }
            }
        }
        return dp[sLenRow][tLenCol];
    }

    //dp空间压缩
    public static int solution3(String s, String t) {
        if (s == null || t == null) {
            return 0;
        }
        //s长度小于t长度 那么g
        if (s.length() < t.length()) {
            return 0;
        }
        int sLenRow = s.length();
        int tLenCol = t.length();
        //当前行只依赖于上一行 和前一列
        int[] dp = new int[tLenCol + 1];
        dp[0] = 1;
        for (int row = 1; row < sLenRow + 1; row++) {
            int[] copy = Arrays.copyOf(dp, dp.length);
            for (int col = 1; col < tLenCol + 1; col++) {
                if (s.charAt(row - 1) == t.charAt(col - 1)) {
                    dp[col] += copy[col - 1];
                }
            }
        }
        return dp[tLenCol];
    }
}
